package com.xiaoyu.binaryTree.basic;

/**
 * @program: DS_and_A
 * @description: 二叉排序树  -->  使用二叉排序树配合中序遍历,就可以实现数组的排序!!!
 * @author: YuWenYi
 * @create: 2021-05-14 08:18
 **/

/*
*        5
*     4     50
*   3      45 58
* 1
*   2
* */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arrs = new int[]{5,4,50,45,3,1,2,58,54,53,52};
        BinarySortTree binarySortTree = new BinarySortTree();

        for (int arr : arrs) {
            binarySortTree.add(new Node(arr));
        }
        binarySortTree.midOrder();
        System.out.println();
        //测试删除叶子结点
        binarySortTree.delNode(50);
        binarySortTree.delNode(5);
        binarySortTree.delNode(4);
        binarySortTree.delNode(45);
        binarySortTree.delNode(52);
        binarySortTree.delNode(58);
        binarySortTree.delNode(54);
        binarySortTree.delNode(53);
        binarySortTree.delNode(1);
        binarySortTree.delNode(2);
        binarySortTree.delNode(3);

        binarySortTree.midOrder();
    }

}

class BinarySortTree{
    Node root;

    //添加结点
    public void add(Node node){
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    //中序遍历
    public void midOrder(){
        if (root!=null){
            root.minOrder();
        }else {
            System.out.println("树为空");
        }
    }
    public Node search(int value){
        if (root!=null){
            return root.search(value);
        }
        return null;
    }
    public Node searchParent(int value){
        if (root!=null){
            return root.searchParent(value);
        }
        return null;
    }

    //删除树中的某个结点(只能删除一个,并且删除后排序树的结构不受影响)
    //考虑三种情况:1.删除叶子结点  2.删除只有一颗子树的结点  3.删除有两颗子树的结点
    public void delNode(int value){
        if (root == null){
            return;
        }else {
            //如果发现当前的二叉树只有一个结点,并且就是要删除的结点,那么就删除它
            if (root.left == null && root.right == null && root.value == value){
                root = null;
                return;
            }
            //找到指定的结点
            Node targetNode = root.search(value);
            if (targetNode == null){
                return;
            }
            //找到指定结点的父节点
            Node parent = root.searchParent(value);
            //targetNode是叶子结点的情况
            if (targetNode.left==null && targetNode.right==null){
               /* if (parent.left!=null && parent.left.value == targetNode.value){
                    parent.left = null;
                }
                if (parent.right!=null && parent.right.value == targetNode.value){
                    parent.right = null;
                }*/
                if (targetNode.value < parent.value){
                    parent.left = null;
                }else {
                    parent.right = null;
                }
            }else if (targetNode.left!=null && targetNode.right!=null){
                //删除的结点既有左子树又有右子树的情况! -->
                //将该结点左子树的最大值 或者 该结点右子树的最小值 与 该要删除的结点进行交换位置 ,然后删除该最大(小)结点
                targetNode.value = delRightTreeMin(targetNode);
            }else {   //删除的结点只有一个孩子的情况!
                if (parent!=null){   //如果不加这个,那么在出现 10 1这种只有两个结点的树的时候,
                                     // 如果删除结点10,parent就会出现空指针异常
                    //如果该孩子是左孩子
                    if (targetNode.left != null){
                        if (targetNode == parent.left){   //如果要删除的结点是其父节点的左结点
                            parent.left = targetNode.left;   //那么就将该结点的左孩子替换到要删除的结点的位置
                        }
                        //同理,如果要删除的结点是其父节点的右结点,就做类似的事情
                        if (targetNode == parent.right){
                            parent.right = targetNode.left;
                        }
                    }
                }else {
                    root = targetNode.left;
                }
                if (parent!=null){
                    //如果该孩子是右孩子
                    if (targetNode.right != null){
                        if (targetNode == parent.left){
                            parent.left = targetNode.right;
                        }
                        if (targetNode == parent.right){
                            parent.right = targetNode.right;
                        }
                    }
                }else {
                    root = targetNode.right;
                }
            }
        }
    }

    //删除以某个结点组成的树的右子树中的最小值,并将这个最小值返回
    public int delRightTreeMin(Node node){
        Node min = node;  //给最小值的结点赋初值
        while (min.left != null){
            min = min.left;
        }
        delNode(min.value);  //此时min一定是叶子结点
        return min.value;
    }

}


class Node{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //查找某个结点
    public Node search(int value){
        if (value == this.value){   //如果值相等,就说明找到结点了,就返回结点
            return this;
        }else if (value < this.value){   //如果值小于当前结点,由于这是二叉排序树,因此递归的去寻找当前结点的左子树即可
            //如果左子节点不为空,才去递归查找左子节点
            if (this.left == null){
                return null;
            }
            return this.left.search(value);   //如果左子树中有任何一个在递归中找到了值,那么就return
        }else {
            //同理,右子结点不为空,才去递归查找右子结点
            if(this.right == null){
                return null;
            }
            return this.right.search(value);  //如果右子树中有任何一个在递归中找到了值,那么就return
        }
    }

    //查找某个结点的父节点
    public Node searchParent(int value){
        //如果当前结点的左孩子或者右孩子是我们要找的结点,那么该结点的父节点就是this
        if ((this.left!=null && this.left.value == value) || (this.right !=null && this.right.value == value)){
            return this;
        }else {
            if (value < this.value && this.left !=null){
                return this.left.searchParent(value);   //向左子树递归查找
            }else if (value >= this.value && this.right != null){
                return this.right.searchParent(value);
            }else {
                return null;  //没有找到父节点,例如是根结点的情况
            }
        }
    }


    //按照二叉排序树的规则,去添加结点
    public void add(Node node){
        if (node == null){
            return;
        }
        if (node.value < this.value){
            if (this.left == null){
                this.left = node;
            }else {
                //递归的往左子树下面找,直到找到合适的位置
                this.left.add(node);
            }
        }else {
            if (this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
    }

    //中序遍历
    public void minOrder(){
        if (this.left != null){
            this.left.minOrder();
        }
        System.out.print(this.value+" ");
        if (this.right != null){
            this.right.minOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
